#include <iostream>
#include <vector>

using namespace std;

bool check[16][16];
int n = 0, m = 0;

int dfs(vector<vector<int>>& grid, int row, int col)
{
    int Max = 0;
    if (row - 1 >= 0 && !check[row - 1][col])
    {
        check[row - 1][col] = true;
        Max = max(Max, dfs(grid, row - 1, col));
        check[row - 1][col] = false;
    }
    if (row + 1 < n && !check[row + 1][col])
    {
        check[row + 1][col] = true;
        Max = max(Max, dfs(grid, row + 1, col));
        check[row + 1][col] = false;
    }
    if (col - 1 >= 0 && !check[row][col - 1])
    {
        check[row][col - 1] = true;
        Max = max(Max, dfs(grid, row, col - 1));
        check[row][col - 1] = false;
    }
    if (col + 1 < m && !check[row][col + 1])
    {
        check[row][col + 1] = true;
        Max = max(Max, dfs(grid, row, col + 1));
        check[row][col + 1] = false;
    }

    return grid[row][col] + Max;
}


int getMaximumGold(vector<vector<int>>& grid)
{
    n = grid.size();
    m = grid[0].size();

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (grid[i][j] == 0)
            {
                check[i][j] = true;
            }
        }
    }

    int ret = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (grid[i][j] != 0)
            {
                check[i][j] = true;
                ret = max(ret, dfs(grid, i, j));
                check[i][j] = false;
            }
        }
    }
    return ret;
}

int main()
{
    vector<vector<int>> grid = { {0,6,0},{0,8,9},{0,9,0} };
    cout << getMaximumGold(grid) << endl;
    return 0;
}